package jm.data.structure.union_find;

/**
 * @Description UnionFind 抽象类
 * @date 2022/5/9 20:28
 */
public abstract class AbstractUnionFind {

    protected int[] parents;

    public AbstractUnionFind(int capacity) {
        // 判断容量是否符合要求
        if (capacity < 0){
            throw new IllegalArgumentException("Capacity must >= 1");
        }
        // 创建基于容量大小的数组
        parents = new int[capacity];

        // 指向自己 让自己作为一个单独的集合
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }
    }

    /**
     * 检测索引是否合法
     * @param index
     */
    protected void rangeCheck(int index){
        if (index >= parents.length || index < 0){
            throw new IndexOutOfBoundsException("Index must less than array's length ");
        }
    }

    /**
     * 查找 v 的 所属集合（根节点）
     * @param v
     * @return
     */
    public abstract int find(int v);

    /**
     * 合并 v1 v2 的所属集合
     * @param v1
     * @param v2
     */
    public abstract void union(int v1, int v2);

    /**
     * 判断 v1 v2 是否属于同一个集合
     * @param v1
     * @param v2
     * @return
     */
    public boolean isSame(int v1, int v2){
        return find(v1) == find(v2);
    }
}
